package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;

import java.util.LinkedList;

/**
 * https://leetcode.com/problems/evaluate-reverse-polish-notation/
 * 后缀表达式求值 逆波兰式
 * 遇到数字直接入栈, 遇到符号运算
 *
 * LC224
 *
 * @author tzp
 * @since 2020/10/24
 */
public class LC150 implements StackProblem {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) return 0;
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            switch (tokens[i]) {
                case "+": {
                    int a = stack.pollLast();
                    int b = stack.pollLast();
                    stack.offerLast(b + a);
                    break;
                }
                case "-": {
                    int a = stack.pollLast();
                    int b = stack.pollLast();
                    stack.offerLast(b - a);
                    break;
                }
                case "*": {
                    int a = stack.pollLast();
                    int b = stack.pollLast();
                    stack.offerLast(b * a);
                    break;
                }
                case "/": {
                    int a = stack.pollLast();
                    int b = stack.pollLast();
                    stack.offerLast(b / a);
                    break;
                }
                default: {
                    stack.offerLast(Integer.valueOf(tokens[i]));
                }
            }
        }
        return stack.peekLast();
    }


    public static void main(String[] args) {
        System.out.println(new LC150().evalRPN(new String[]{
                "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"
        }));
    }
}
